{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 第5章 决策树\n",
    "\n",
    "## 习题5.1\n",
    "&emsp;&emsp;根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "表5.1 贷款申请样本数据表  \n",
    "\n",
    "ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别\n",
    ":-: | :-: | :-: | :-: | :-: | :-: \n",
    "1 | 青年 | 否 | 否 | 一般 | 否\n",
    "2 | 青年 | 否 | 否 | 好 | 否\n",
    "3 | 青年 | 是 | 否 | 好 | 是\n",
    "4 | 青年 | 是 | 是 | 一般 | 是\n",
    "5 | 青年 | 否 | 否 | 一般 | 否\n",
    "6 | 中年 | 否 | 否 | 一般 | 否\n",
    "7 | 中年 | 否 | 否 | 好 | 否\n",
    "8 | 中年 | 是 | 是 | 好 | 是\n",
    "9 | 中年 | 否 | 是 | 非常好 | 是\n",
    "10 | 中年 | 否 | 是 | 非常好 | 是\n",
    "11 | 老年 | 否 | 是 | 非常好 | 是\n",
    "12 | 老年 | 否 | 是 | 好 | 是\n",
    "13 | 老年 | 是 | 否 | 好 | 是\n",
    "14 | 老年 | 是 | 否 | 非常好 | 是\n",
    "15 | 老年 | 否 | 否 | 一般 | 否"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**  \n",
    "1. 列出C4.5的生成算法；\n",
    "2. 使用sklearn的DecisionTreeClassifier类构建决策树，并使用graphviz包展示，默认是Gini，这里可以作为自编程的验证\n",
    "3. 通过自编程实现C4.5算法生成决策树，并进行特征选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解题步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：C4.5的生成算法（书中第78页）**  \n",
    "\n",
    "> 输入：训练数据集$D$，特征集$A$阈值$\\epsilon$；  \n",
    "输出：决策树$T$。  \n",
    "（1）如果$D$中所有实例属于同一类$C_k$，则置$T$为单结点树，并将$C_k$作为该结点的类，返回$T$；  \n",
    "（2）如果$A = \\emptyset$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类，返回$T$；  \n",
    "（3）否则，按式$\\displaystyle g_R(D,A)=\\frac{g(D,A)}{H_A(D)}$计算$A$中各特征对$D$的信息增益比，选择信息增益比最大的特征$A_g$；  \n",
    "（4）如果$A_g$的信息增益比小于阈值$\\epsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类，返回$T$；  \n",
    "（5）否则，对$A_g$的每一可能值$a_i$，依$A_g=a_i$将$D$分割为子集若干非空$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；  \n",
    "（6）对结点$i$，以$D_i$为训练集，以$A-\\{A_g\\}$为特征集，递归地调用步(1)~步(5)，得到子树$T_i$，返回$T_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：调用sklearn的DecisionTreeClassifier类构建决策树**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.47.3 (20210619.1520)\r\n",
       " -->\r\n",
       "<!-- Title: Tree Pages: 1 -->\r\n",
       "<svg width=\"340pt\" height=\"314pt\"\r\n",
       " viewBox=\"0.00 0.00 340.00 314.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 310)\">\r\n",
       "<title>Tree</title>\r\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-310 336,-310 336,4 -4,4\"/>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node1\" class=\"node\">\r\n",
       "<title>0</title>\r\n",
       "<path fill=\"#bddef6\" stroke=\"black\" d=\"M266,-306C266,-306 136,-306 136,-306 130,-306 124,-300 124,-294 124,-294 124,-235 124,-235 124,-229 130,-223 136,-223 136,-223 266,-223 266,-223 272,-223 278,-229 278,-235 278,-235 278,-294 278,-294 278,-300 272,-306 266,-306\"/>\r\n",
       "<text text-anchor=\"start\" x=\"132\" y=\"-290.8\" font-family=\"SimSun\" font-size=\"14.00\">有自己的房子 ≤ 3.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"159.5\" y=\"-275.8\" font-family=\"SimSun\" font-size=\"14.00\">gini = 0.48</text>\r\n",
       "<text text-anchor=\"start\" x=\"155.5\" y=\"-260.8\" font-family=\"SimSun\" font-size=\"14.00\">samples = 15</text>\r\n",
       "<text text-anchor=\"start\" x=\"148\" y=\"-245.8\" font-family=\"SimSun\" font-size=\"14.00\">value = [6, 9]</text>\r\n",
       "<text text-anchor=\"start\" x=\"163.5\" y=\"-230.8\" font-family=\"SimSun\" font-size=\"14.00\">class = 是</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\">\r\n",
       "<title>1</title>\r\n",
       "<path fill=\"#f2c09c\" stroke=\"black\" d=\"M180,-187C180,-187 82,-187 82,-187 76,-187 70,-181 70,-175 70,-175 70,-116 70,-116 70,-110 76,-104 82,-104 82,-104 180,-104 180,-104 186,-104 192,-110 192,-116 192,-116 192,-175 192,-175 192,-181 186,-187 180,-187\"/>\r\n",
       "<text text-anchor=\"start\" x=\"83.5\" y=\"-171.8\" font-family=\"SimSun\" font-size=\"14.00\">有工作 ≤ 3.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"85.5\" y=\"-156.8\" font-family=\"SimSun\" font-size=\"14.00\">gini = 0.444</text>\r\n",
       "<text text-anchor=\"start\" x=\"89.5\" y=\"-141.8\" font-family=\"SimSun\" font-size=\"14.00\">samples = 9</text>\r\n",
       "<text text-anchor=\"start\" x=\"78\" y=\"-126.8\" font-family=\"SimSun\" font-size=\"14.00\">value = [6, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"93.5\" y=\"-111.8\" font-family=\"SimSun\" font-size=\"14.00\">class = 否</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\">\r\n",
       "<title>0&#45;&gt;1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.71,-222.91C171.45,-214.1 165.82,-204.7 160.38,-195.61\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"163.38,-193.81 155.24,-187.02 157.37,-197.4 163.38,-193.81\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"149.15\" y=\"-207.57\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">True</text>\r\n",
       "</g>\r\n",
       "<!-- 4 -->\r\n",
       "<g id=\"node5\" class=\"node\">\r\n",
       "<title>4</title>\r\n",
       "<path fill=\"#399de5\" stroke=\"black\" d=\"M320,-179.5C320,-179.5 222,-179.5 222,-179.5 216,-179.5 210,-173.5 210,-167.5 210,-167.5 210,-123.5 210,-123.5 210,-117.5 216,-111.5 222,-111.5 222,-111.5 320,-111.5 320,-111.5 326,-111.5 332,-117.5 332,-123.5 332,-123.5 332,-167.5 332,-167.5 332,-173.5 326,-179.5 320,-179.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"233\" y=\"-164.3\" font-family=\"SimSun\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"229.5\" y=\"-149.3\" font-family=\"SimSun\" font-size=\"14.00\">samples = 6</text>\r\n",
       "<text text-anchor=\"start\" x=\"218\" y=\"-134.3\" font-family=\"SimSun\" font-size=\"14.00\">value = [0, 6]</text>\r\n",
       "<text text-anchor=\"start\" x=\"233.5\" y=\"-119.3\" font-family=\"SimSun\" font-size=\"14.00\">class = 是</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\">\r\n",
       "<title>0&#45;&gt;4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M225.29,-222.91C231.95,-211.76 239.2,-199.66 245.91,-188.44\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"249.03,-190.05 251.16,-179.67 243.02,-186.45 249.03,-190.05\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"257.25\" y=\"-200.21\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">False</text>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\">\r\n",
       "<title>2</title>\r\n",
       "<path fill=\"#e58139\" stroke=\"black\" d=\"M110,-68C110,-68 12,-68 12,-68 6,-68 0,-62 0,-56 0,-56 0,-12 0,-12 0,-6 6,0 12,0 12,0 110,0 110,0 116,0 122,-6 122,-12 122,-12 122,-56 122,-56 122,-62 116,-68 110,-68\"/>\r\n",
       "<text text-anchor=\"start\" x=\"23\" y=\"-52.8\" font-family=\"SimSun\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"19.5\" y=\"-37.8\" font-family=\"SimSun\" font-size=\"14.00\">samples = 6</text>\r\n",
       "<text text-anchor=\"start\" x=\"8\" y=\"-22.8\" font-family=\"SimSun\" font-size=\"14.00\">value = [6, 0]</text>\r\n",
       "<text text-anchor=\"start\" x=\"23.5\" y=\"-7.8\" font-family=\"SimSun\" font-size=\"14.00\">class = 否</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;2 -->\r\n",
       "<g id=\"edge2\" class=\"edge\">\r\n",
       "<title>1&#45;&gt;2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.93,-103.73C99.34,-94.97 93.41,-85.7 87.79,-76.91\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"90.62,-74.84 82.29,-68.3 84.72,-78.61 90.62,-74.84\"/>\r\n",
       "</g>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node4\" class=\"node\">\r\n",
       "<title>3</title>\r\n",
       "<path fill=\"#399de5\" stroke=\"black\" d=\"M250,-68C250,-68 152,-68 152,-68 146,-68 140,-62 140,-56 140,-56 140,-12 140,-12 140,-6 146,0 152,0 152,0 250,0 250,0 256,0 262,-6 262,-12 262,-12 262,-56 262,-56 262,-62 256,-68 250,-68\"/>\r\n",
       "<text text-anchor=\"start\" x=\"163\" y=\"-52.8\" font-family=\"SimSun\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"159.5\" y=\"-37.8\" font-family=\"SimSun\" font-size=\"14.00\">samples = 3</text>\r\n",
       "<text text-anchor=\"start\" x=\"148\" y=\"-22.8\" font-family=\"SimSun\" font-size=\"14.00\">value = [0, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"163.5\" y=\"-7.8\" font-family=\"SimSun\" font-size=\"14.00\">class = 是</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;3 -->\r\n",
       "<g id=\"edge3\" class=\"edge\">\r\n",
       "<title>1&#45;&gt;3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M157.07,-103.73C162.66,-94.97 168.59,-85.7 174.21,-76.91\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"177.28,-78.61 179.71,-68.3 171.38,-74.84 177.28,-78.61\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x1dc5348bb08>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn import preprocessing\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from sklearn import tree\n",
    "import graphviz\n",
    "\n",
    "features = [\"年龄\", \"有工作\", \"有自己的房子\", \"信贷情况\"]\n",
    "X_train = pd.DataFrame([\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"是\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"好\"],\n",
    "    [\"中年\", \"是\", \"是\", \"好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"否\", \"一般\"]\n",
    "])\n",
    "y_train = pd.DataFrame([\"否\", \"否\", \"是\", \"是\", \"否\",\n",
    "                        \"否\", \"否\", \"是\", \"是\", \"是\",\n",
    "                        \"是\", \"是\", \"是\", \"是\", \"否\"])\n",
    "class_names = [str(k) for k in np.unique(y_train)]\n",
    "# 数据预处理\n",
    "le_x = preprocessing.LabelEncoder()\n",
    "le_x.fit(np.unique(X_train))\n",
    "X_train = X_train.apply(le_x.transform)\n",
    "# 调用sklearn的DecisionTreeClassifier建立决策树模型\n",
    "model_tree = DecisionTreeClassifier()\n",
    "# 训练模型\n",
    "model_tree.fit(X_train, y_train)\n",
    "\n",
    "# 导出决策树的可视化文件，文件格式是dot\n",
    "dot_data = tree.export_graphviz(model_tree, out_file=None,\n",
    "                                feature_names=features,\n",
    "                                class_names=class_names,\n",
    "                                filled=True, rounded=True,\n",
    "                                special_characters=True)\n",
    "# 使用graphviz包，对决策树进行展示\n",
    "graph = graphviz.Source(dot_data)\n",
    "# 可使用view方法展示决策树\n",
    "# 中文乱码：需要对源码_export.py文件（文件路径：sklearn/tree/_export.py）修改，\n",
    "# 在文件第451行中将helvetica改成SimSun\n",
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|--- 有自己的房子 <= 3.00\n",
      "|   |--- 有工作 <= 3.00\n",
      "|   |   |--- class: 否\n",
      "|   |--- 有工作 >  3.00\n",
      "|   |   |--- class: 是\n",
      "|--- 有自己的房子 >  3.00\n",
      "|   |--- class: 是\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 打印决策树\n",
    "tree_text = tree.export_text(model_tree, feature_names=features)\n",
    "print(tree_text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第3步：自编程实现C4.5算法生成决策树**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "from collections import Counter\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "# 节点类\n",
    "class Node:\n",
    "    def __init__(self, node_type, class_name, feature_name=None,\n",
    "                 info_gain_ratio_value=0.0):\n",
    "        # 结点类型（internal或leaf）\n",
    "        self.node_type = node_type\n",
    "        # 特征名\n",
    "        self.feature_name = feature_name\n",
    "        # 类别名\n",
    "        self.class_name = class_name\n",
    "        # 子结点树\n",
    "        self.child_nodes = []\n",
    "        # Gini指数值\n",
    "        self.info_gain_ratio_value = info_gain_ratio_value\n",
    "\n",
    "    def __repr__(self):\n",
    "        return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False)\n",
    "\n",
    "    def add_sub_tree(self, key, sub_tree):\n",
    "        self.child_nodes.append({\"condition\": key, \"sub_tree\": sub_tree})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyDecisionTree:\n",
    "    def __init__(self, epsilon):\n",
    "        self.epsilon = epsilon\n",
    "        self.tree = None\n",
    "\n",
    "    def fit(self, train_set, y, feature_names):\n",
    "        features_indices = list(range(len(feature_names)))\n",
    "        self.tree = self._fit(train_set, y, features_indices, feature_names)\n",
    "        return self\n",
    "\n",
    "    # C4.5算法\n",
    "    def _fit(self, train_data, y, features_indices, feature_labels):\n",
    "        LEAF = 'leaf'\n",
    "        INTERNAL = 'internal'\n",
    "        class_num = len(np.unique(y))\n",
    "\n",
    "        # （1）如果训练数据集所有实例都属于同一类Ck\n",
    "        label_set = set(y)\n",
    "        if len(label_set) == 1:\n",
    "            # 将Ck作为该结点的类\n",
    "            return Node(node_type=LEAF, class_name=label_set.pop())\n",
    "\n",
    "        # （2）如果特征集为空\n",
    "        # 计算每一个类出现的个数\n",
    "        class_len = Counter(y).most_common()\n",
    "        (max_class, max_len) = class_len[0]\n",
    "\n",
    "        if len(features_indices) == 0:\n",
    "            # 将实例数最大的类Ck作为该结点的类\n",
    "            return Node(LEAF, class_name=max_class)\n",
    "\n",
    "        # （3）按式(5.10)计算信息增益，并选择信息增益最大的特征\n",
    "        max_feature = 0\n",
    "        max_gda = 0\n",
    "        D = y.copy()\n",
    "        # 计算特征集A中各特征\n",
    "        for feature in features_indices:\n",
    "            # 选择训练集中的第feature列（即第feature个特征）\n",
    "            A = np.array(train_data[:, feature].flat)\n",
    "            # 计算信息增益\n",
    "            gda = self._calc_ent_grap(A, D)\n",
    "            if self._calc_ent(A) != 0:\n",
    "                # 计算信息增益比\n",
    "                gda /= self._calc_ent(A)\n",
    "            # 选择信息增益最大的特征Ag\n",
    "            if gda > max_gda:\n",
    "                max_gda, max_feature = gda, feature\n",
    "\n",
    "        # （4）如果Ag信息增益小于阈值\n",
    "        if max_gda < self.epsilon:\n",
    "            # 将训练集中实例数最大的类Ck作为该结点的类\n",
    "            return Node(LEAF, class_name=max_class)\n",
    "\n",
    "        max_feature_label = feature_labels[max_feature]\n",
    "\n",
    "        # （6）移除已选特征Ag\n",
    "        sub_feature_indecs = np.setdiff1d(features_indices, max_feature)\n",
    "        sub_feature_labels = np.setdiff1d(feature_labels, max_feature_label)\n",
    "\n",
    "        # （5）构建非空子集\n",
    "        # 构建结点\n",
    "        feature_name = feature_labels[max_feature]\n",
    "        tree = Node(INTERNAL, class_name=None, feature_name=feature_name,\n",
    "                    info_gain_ratio_value=max_gda)\n",
    "\n",
    "        max_feature_col = np.array(train_data[:, max_feature].flat)\n",
    "        # 将类按照对应的实例数递减顺序排列\n",
    "        feature_value_list = [x[0] for x in Counter(max_feature_col).most_common()]\n",
    "        # 遍历Ag的每一个可能值ai\n",
    "        for feature_value in feature_value_list:\n",
    "            index = []\n",
    "            for i in range(len(y)):\n",
    "                if train_data[i][max_feature] == feature_value:\n",
    "                    index.append(i)\n",
    "\n",
    "            # 递归调用步（1）~步（5），得到子树\n",
    "            sub_train_set = train_data[index]\n",
    "            sub_train_label = y[index]\n",
    "            sub_tree = self._fit(sub_train_set, sub_train_label, sub_feature_indecs, sub_feature_labels)\n",
    "            # 在结点中，添加其子结点构成的树\n",
    "            tree.add_sub_tree(feature_value, sub_tree)\n",
    "\n",
    "        return tree\n",
    "\n",
    "    # 计算数据集x的经验熵H(x)\n",
    "    def _calc_ent(self, x):\n",
    "        x_value_list = set([x[i] for i in range(x.shape[0])])\n",
    "        ent = 0.0\n",
    "        for x_value in x_value_list:\n",
    "            p = float(x[x == x_value].shape[0]) / x.shape[0]\n",
    "            logp = np.log2(p)\n",
    "            ent -= p * logp\n",
    "\n",
    "        return ent\n",
    "\n",
    "    # 计算条件熵H(y/x)\n",
    "    def _calc_condition_ent(self, x, y):\n",
    "        x_value_list = set([x[i] for i in range(x.shape[0])])\n",
    "        ent = 0.0\n",
    "        for x_value in x_value_list:\n",
    "            sub_y = y[x == x_value]\n",
    "            temp_ent = self._calc_ent(sub_y)\n",
    "            ent += (float(sub_y.shape[0]) / y.shape[0]) * temp_ent\n",
    "\n",
    "        return ent\n",
    "\n",
    "    # 计算信息增益\n",
    "    def _calc_ent_grap(self, x, y):\n",
    "        base_ent = self._calc_ent(y)\n",
    "        condition_ent = self._calc_condition_ent(x, y)\n",
    "        ent_grap = base_ent - condition_ent\n",
    "\n",
    "        return ent_grap\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{\n",
       "   \"node_type\": \"internal\",\n",
       "   \"feature_name\": \"有自己的房子\",\n",
       "   \"class_name\": null,\n",
       "   \"child_nodes\": [\n",
       "      {\n",
       "         \"condition\": \"否\",\n",
       "         \"sub_tree\": {\n",
       "            \"node_type\": \"internal\",\n",
       "            \"feature_name\": \"年龄\",\n",
       "            \"class_name\": null,\n",
       "            \"child_nodes\": [\n",
       "               {\n",
       "                  \"condition\": \"否\",\n",
       "                  \"sub_tree\": {\n",
       "                     \"node_type\": \"leaf\",\n",
       "                     \"feature_name\": null,\n",
       "                     \"class_name\": \"否\",\n",
       "                     \"child_nodes\": [],\n",
       "                     \"info_gain_ratio_value\": 0.0\n",
       "                  }\n",
       "               },\n",
       "               {\n",
       "                  \"condition\": \"是\",\n",
       "                  \"sub_tree\": {\n",
       "                     \"node_type\": \"leaf\",\n",
       "                     \"feature_name\": null,\n",
       "                     \"class_name\": \"是\",\n",
       "                     \"child_nodes\": [],\n",
       "                     \"info_gain_ratio_value\": 0.0\n",
       "                  }\n",
       "               }\n",
       "            ],\n",
       "            \"info_gain_ratio_value\": 1.0\n",
       "         }\n",
       "      },\n",
       "      {\n",
       "         \"condition\": \"是\",\n",
       "         \"sub_tree\": {\n",
       "            \"node_type\": \"leaf\",\n",
       "            \"feature_name\": null,\n",
       "            \"class_name\": \"是\",\n",
       "            \"child_nodes\": [],\n",
       "            \"info_gain_ratio_value\": 0.0\n",
       "         }\n",
       "      }\n",
       "   ],\n",
       "   \"info_gain_ratio_value\": 0.4325380677663126\n",
       "}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 表5.1的训练数据集\n",
    "feature_names = np.array([\"年龄\", \"有工作\", \"有自己的房子\", \"信贷情况\"])\n",
    "X_train = np.array([\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"是\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"好\"],\n",
    "    [\"中年\", \"是\", \"是\", \"好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"否\", \"一般\"]\n",
    "])\n",
    "y = np.array([\"否\", \"否\", \"是\", \"是\", \"否\",\n",
    "              \"否\", \"否\", \"是\", \"是\", \"是\",\n",
    "              \"是\", \"是\", \"是\", \"是\", \"否\"])\n",
    "\n",
    "dt_tree = MyDecisionTree(epsilon=0.1)\n",
    "dt_tree.fit(X_train, y, feature_names)\n",
    "dt_tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题5.2\n",
    "&emsp;&emsp;已知如表5.2所示的训练数据，试用平方误差损失准则生成一个二叉回归树。  \n",
    "表5.2 训练数据表  \n",
    "\n",
    "| $x_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |  \n",
    "| - | - | - | - | - | - | - | - | - | - | - |  \n",
    "| $y_i$ | 4.50 | 4.75 | 4.91 | 5.34 | 5.80 | 7.05 | 7.90 | 8.23 | 8.70 | 9.00"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**\n",
    "1. 根据书中第81页平方误差损失准则，列出最小二乘回归树生成算法（算法5.5）；\n",
    "2. 编写代码，实现算法，并用表5.2训练数据进行验证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解题步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：算法5.5的最小二乘回归树生成算法（书中第82页）**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> &emsp;&emsp;决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。\n",
    "> \n",
    "> 算法5.5（最小二乘回归树生成算法）  \n",
    "输入：训练数据集$D$  \n",
    "输出：回归树$f(x)$  \n",
    "在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树；  \n",
    "(1)选择最优切分变量$j$与切分点$s$，求解\n",
    "> $$\n",
    "\\min_{j,s} \\left[ \\min_{c_1} \\sum_{x_i \\in R_1(j,s)} (y_i - c_1)^2 + \\min_{c_2} \\sum_{x_i \\in R_2(j,s)} (y_i - c_2)^2\\right]\n",
    "$$\n",
    "> 遍历变量$j$，对固定的切分变量$j$扫描切分点$s$，选择使得上式达到最小值的对$(j,s)$  \n",
    "(2)用选定的对$(j,s)$划分区域并决定相应的输出值：\n",
    "> $$\n",
    "R_1(j,s)=\\{x|x^{(j)}\\leqslant s\\}, R_2(j,s)=\\{x|x^{(j)} > s\\} \\\\ \n",
    "\\hat{c}_m = \\frac{1}{N_m} \\sum_{x_i \\in R_m(j,s)} y_i, x \\in R_m, m=1,2 \n",
    "$$\n",
    "> (3)继续对两个子区域调用步骤(1),(2)，直至满足停止条件  \n",
    "(4)将输入空间划分为$M$个区域$R_1,R_2,\\cdots,R_M$，生成决策树：\n",
    "> $$\n",
    "f(x)=\\sum_{m=1}^M \\hat{c}_m I(x \\in R_m)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：编写代码，实现算法，并用表5.2训练数据进行验证**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "# 节点类\n",
    "class Node:\n",
    "    def __init__(self, value, feature, left=None, right=None):\n",
    "        self.value = value.tolist()\n",
    "        self.feature = feature.tolist()\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def __repr__(self):\n",
    "        return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyLeastSquareRegTree:\n",
    "    def __init__(self, train_X, y, epsilon):\n",
    "        # 训练集特征值\n",
    "        self.x = train_X\n",
    "        # 类别\n",
    "        self.y = y\n",
    "        # 特征总数\n",
    "        self.feature_count = train_X.shape[1]\n",
    "        # 损失阈值\n",
    "        self.epsilon = epsilon\n",
    "        # 回归树\n",
    "        self.tree = None\n",
    "\n",
    "    def _fit(self, x, y, feature_count):\n",
    "        # （1）选择最优切分点变量j与切分点s，得到选定的对(j,s)，并解得c1，c2\n",
    "        (j, s, minval, c1, c2) = self._divide(x, y, feature_count)\n",
    "        # 初始化树\n",
    "        tree = Node(feature=j, value=x[s, j], left=None, right=None)\n",
    "        # 用选定的对(j,s)划分区域，并确定响应的输出值\n",
    "        if minval < self.epsilon or len(y[np.where(x[:, j] <= x[s, j])]) <= 1:\n",
    "            tree.left = c1\n",
    "        else:\n",
    "            # 对左子区域调用步骤（1）、（2）\n",
    "            tree.left = self._fit(x[np.where(x[:, j] <= x[s, j])],\n",
    "                                  y[np.where(x[:, j] <= x[s, j])],\n",
    "                                  self.feature_count)\n",
    "        if minval < self.epsilon or len(y[np.where(x[:, j] > s)]) <= 1:\n",
    "            tree.right = c2\n",
    "        else:\n",
    "            # 对右子区域调用步骤（1）、（2）\n",
    "            tree.right = self._fit(x[np.where(x[:, j] > x[s, j])],\n",
    "                                   y[np.where(x[:, j] > x[s, j])],\n",
    "                                   self.feature_count)\n",
    "        return tree\n",
    "\n",
    "    def fit(self):\n",
    "        self.tree = self._fit(self.x, self.y, self.feature_count)\n",
    "        return self\n",
    "\n",
    "    @staticmethod\n",
    "    def _divide(x, y, feature_count):\n",
    "        # 初始化损失误差\n",
    "        cost = np.zeros((feature_count, len(x)))\n",
    "        # 公式5.21\n",
    "        for i in range(feature_count):\n",
    "            for k in range(len(x)):\n",
    "                # k行i列的特征值\n",
    "                value = x[k, i]\n",
    "                y1 = y[np.where(x[:, i] <= value)]\n",
    "                c1 = np.mean(y1)\n",
    "                y2 = y[np.where(x[:, i] > value)]\n",
    "                if len(y2) == 0:\n",
    "                    c2 = 0\n",
    "                else:\n",
    "                    c2 = np.mean(y2)\n",
    "                y1[:] = y1[:] - c1\n",
    "                y2[:] = y2[:] - c2\n",
    "                cost[i, k] = np.sum(y1 * y1) + np.sum(y2 * y2)\n",
    "        # 选取最优损失误差点\n",
    "        cost_index = np.where(cost == np.min(cost))\n",
    "        # 所选取的特征\n",
    "        j = cost_index[0][0]\n",
    "        # 选取特征的切分点\n",
    "        s = cost_index[1][0]\n",
    "        # 求两个区域的均值c1,c2\n",
    "        c1 = np.mean(y[np.where(x[:, j] <= x[s, j])])\n",
    "        c2 = np.mean(y[np.where(x[:, j] > x[s, j])])\n",
    "        return j, s, cost[cost_index], c1, c2\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{\n",
       "   \"value\": 5,\n",
       "   \"feature\": 0,\n",
       "   \"left\": {\n",
       "      \"value\": 3,\n",
       "      \"feature\": 0,\n",
       "      \"left\": 4.72,\n",
       "      \"right\": 5.57\n",
       "   },\n",
       "   \"right\": {\n",
       "      \"value\": 7,\n",
       "      \"feature\": 0,\n",
       "      \"left\": {\n",
       "         \"value\": 6,\n",
       "         \"feature\": 0,\n",
       "         \"left\": 7.05,\n",
       "         \"right\": 7.9\n",
       "      },\n",
       "      \"right\": {\n",
       "         \"value\": 8,\n",
       "         \"feature\": 0,\n",
       "         \"left\": 8.23,\n",
       "         \"right\": 8.85\n",
       "      }\n",
       "   }\n",
       "}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "train_X = np.array([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]).T\n",
    "y = np.array([4.50, 4.75, 4.91, 5.34, 5.80, 7.05, 7.90, 8.23, 8.70, 9.00])\n",
    "\n",
    "model_tree = MyLeastSquareRegTree(train_X, y, epsilon=0.2)\n",
    "model_tree.fit()\n",
    "model_tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上面程序的输出，可得到用平方误差损失准则生成一个二叉回归树：$$f(x)=\\begin{cases}\n",
    "4.72 & x \\le 3\\\\\n",
    "5.57 & 3 < x \\le 5\\\\\n",
    "7.05 & 5 < x \\le 6\\\\\n",
    "7.9 & 6 < x \\le 7 \\\\\n",
    "8.23 & 7 < x \\le 8\\\\\n",
    "8.85 & x > 8\\\\\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题5.3\n",
    "\n",
    "&emsp;&emsp;证明 CART 剪枝算法中，当$\\alpha$确定时，存在唯一的最小子树$T_{\\alpha}$使损失函数$C_{\\alpha}(T)$最小。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**\n",
    "1. 列出CART剪枝算法；\n",
    "2. 列出树的剪枝算法；\n",
    "3. 采用反证法，假设存在两棵子树使得损失函数最小。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：CART剪枝算法（书中第87页）**\n",
    "> 输入：CART算法生成的决策树$T_0$；  \n",
    "输出：最优决策树$T_\\alpha$。  \n",
    "> （1）设$k=0,T=T_0$。  \n",
    "（2）设$\\alpha=+\\infty$。  \n",
    "（3）自下而上地对各内部结点$t$计算$C(T_t)$,$|T_t|$，以及\n",
    "> $$\n",
    "g(t)=\\cfrac{C(t)-C(T_t)}{|T_t|-1} \\\\\n",
    "\\alpha = \\min(\\alpha,g(t))\n",
    "$$\n",
    "> 这里，$T_t$表示以$t$为根结点的子树，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶结点个数。  \n",
    "（4）对$g(t)=\\alpha$的内部结点$t$进行剪枝，并对叶结点$t$以多数表决法决定其类，得到树$T$。  \n",
    "（5）设$k=k+1,\\alpha_k=\\alpha,T_k=T$。  \n",
    "（6）如果$T_k$不是由根节点和两个叶结点组成的树，则回到步骤（2），否则$T_k=T_n$。  \n",
    "（7）采用交叉验证法在子树序列从$T_0,T_1,\\cdots,T_n$中选取最优子树$T_{\\alpha}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：树的剪枝算法（书中第79页）**\n",
    "> 输入：生成算法产生的整个树$T$，参数$\\alpha$；  \n",
    "输出：修剪后的子树$T_\\alpha$。  \n",
    "（1）计算每个结点的经验熵。  \n",
    "（2）递归地从树的叶结点向上回缩。  \n",
    "&emsp;&emsp;设一组叶结点回缩到其父结点之前与之后的整体树分别为$T_B$与$T_A$，其对应的损失函数分别是$C_\\alpha(T_B)$与$C_\\alpha(T_A)$，如果\n",
    ">$$\n",
    "C_\\alpha(T_A) \\leqslant C_\\alpha(T_B)\n",
    "$$\n",
    "> 则进行剪枝，即将父结点变为新的叶结点。  \n",
    "（3）返回（2），直至不能继续为止，得到损失函数最小的子树$T_\\alpha$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第3步：采用反证法，假设存在两棵子树使得损失函数最小**  \n",
    "\n",
    "&emsp;&emsp;从第1、2步可得到以下结论：\n",
    "1. 内部节点是否剪枝只与以该节点为根节点的子树有关；\n",
    "2. 当$C_\\alpha(t) < C_\\alpha(T_t)$时，对以结点$t$为根节点的子树进行剪枝。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br/><center>\n",
    "<img src=\"./images/5-1-prune.png\" style=\"zoom: 50%;\"><br/><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图5.1 树$T_1$存在两个最优子树$T_2,T_3$</div></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;如图5.1所示，整个树$T_1$有两个子树$T_2$和$T_3$，其剪枝位置分别为$t_2$和$t_3$，假设两棵子树都是$T_1$的最优子树，使得损失函数最小。则满足以下等式：\n",
    "$$\n",
    "C_{\\alpha}(T_2)=C_{\\alpha}(T_3) \n",
    "$$ \n",
    "&emsp;&emsp;根据子树$T_2$的剪枝位置是$t_2$，可得\n",
    "$$\n",
    "C_{\\alpha}(t_2)<C_{\\alpha}(T_2) \n",
    "$$\n",
    "&emsp;&emsp;根据子树$T_3$的剪枝位置是$t_3$，可得\n",
    "$$\n",
    "C_{\\alpha}(t_3)<C_{\\alpha}(T_3)\n",
    "$$\n",
    "&emsp;&emsp;由上面公式可得：\n",
    "$$\n",
    "C_{\\alpha}(t_2)<C_{\\alpha}(T_3) \\\\\n",
    "C_{\\alpha}(t_3)<C_{\\alpha}(T_2)\n",
    "$$\n",
    "&emsp;&emsp;根据上述公式，可知$T_2$和$T_3$都可以进一步剪枝，剪枝之后的子树记作$T_4$："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br/><center>\n",
    "<img src=\"./images/5-2-prune-T4.png\" style=\"zoom: 50%;\"><br/><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图5.2 剪枝后的子树$T_4$</div></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;因此，如果存在两棵以上的最优子树，其中一棵树总能找到一个来自另一棵子树的剪枝点，使得整体损失进一步下降，所以只能存在唯一的最小子树使得损失函数最小，得证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题5.4\n",
    "\n",
    "&emsp;&emsp;证明 CART 剪枝算法中求出的子树序列$\\{T_0,T_1,\\cdots,T_n\\}$分别是区间$\\alpha \\in [\\alpha_i,\\alpha_{i+1})$的最优子树$T_{\\alpha}$，这里$i=0,1,\\cdots,n,0=\\alpha_0 < \\alpha_1 < \\cdots, \\alpha_n < +\\infty$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**\n",
    "1. 对题目重新进行表述；\n",
    "2. 证明当$\\alpha=0$和$\\alpha= + \\infty$时的最优子树；\n",
    "3. 证明$T_1$为区间$[\\alpha_1,\\alpha_2)$的最优子树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：对题目重新表述**  \n",
    "&emsp;&emsp;原结论可以表述为：将$\\alpha$从$0$增大到$+\\infty$（即$0=\\alpha_0<\\alpha_1<\\cdots<\\alpha_n < +\\infty$），在每个区间$[\\alpha_i,\\alpha_{i+1})$中，其中$i=0,1,\\ldots,n$，子树$T_i$是该区间里最优的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：证明当$\\alpha=0$和$\\alpha= + \\infty$时的最优子树**\n",
    "\n",
    "根据书中第85页：\n",
    "> &emsp;&emsp;当$\\alpha$大的时候，最优子树$T_\\alpha$偏小；当$\\alpha$小的时候，最优子树$T_\\alpha$偏大。极端情况，当$\\alpha=0$时，整体树是最优的。当$\\alpha \\rightarrow +\\infty$时，根结点组成的单结点树是最优的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第3步：证明$T_1$是区间$[\\alpha_1, \\alpha_2)$的最优子树**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据《Classification and Regression Trees》书中第10.2节的定理10.7：\n",
    "> THEOREM 10.7. Every tree T has a unique smallest optimally pruned subtree $T(\\alpha)$. Let T be a nontrivial tree having root $t_1$ and primary branches $T_L$ and $T_R$. Then $$R_{\\alpha}(T(\\alpha)) = \\min[R_{\\alpha}(t_1), R_{\\alpha}(T_L(\\alpha))+R_{\\alpha}(T_R(\\alpha))]$$ If $R_{\\alpha}(t_1) \\leqslant R_{\\alpha}(T_L(\\alpha))+R_{\\alpha}(T_R(\\alpha))$, then $T(\\alpha)=\\{t_1\\}$; otherwise, $T(\\alpha) = \\{t_1\\} \\cup T_L(\\alpha) \\cup T_R(\\alpha)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据该书的符号描述，其中：\n",
    "1. $T(\\alpha)$表示，在$\\alpha$条件时，树$T$的最小最优剪枝子树\n",
    "2. $R_{\\alpha}(T(\\alpha))$表示，在$\\alpha$条件时，$T(\\alpha)$的损失值，即$C_{\\alpha}(T_{\\alpha})$\n",
    "\n",
    "&emsp;&emsp;定理10.7表示，树$T$分为根结点$t_1$、左子树$T_L$和右子树$T_R$，计算在$\\alpha$条件时的最优子树的损失，可取$R_{\\alpha}(t_1)$和$R_{\\alpha}(T_L(\\alpha))+R_{\\alpha}(T_R(\\alpha))$中的最小值，并且$T(\\alpha)$满足以下公式：\n",
    "$$\n",
    "T(\\alpha) = \\left\\{ \\begin{array}{l}\n",
    "\\{t_1 \\}, \\quad R_{\\alpha}(t_1) \\leqslant R_{\\alpha}(T_L(\\alpha))+R_{\\alpha}(T_R(\\alpha)) \\\\\n",
    "\\{t_1\\} \\cup T_L(\\alpha) \\cup T_R(\\alpha), \\quad \\text{otherwise}\n",
    "\\end{array}\\right.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据定理10.7，可以得到该书定理10.9的第一个推论：\n",
    "> THEOREM 10.9.   \n",
    "(i) If $\\alpha_2 \\geqslant \\alpha_1$, then $T(α2) \\preceq T(α1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;定理10.9(i)表示，当$\\alpha_2 \\geqslant \\alpha_1$时，树$T$在$\\alpha_2$条件下的最优子树一定是树$T$在$\\alpha_1$条件下的最优子树的子树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据CART剪枝算法和定理10.9，可知（见该书的第368页）：\n",
    "1. 当$\\alpha \\geqslant \\alpha_1$时，$T_0(\\alpha)=T_1$\n",
    "2. 当$\\alpha_1 \\leqslant \\alpha < \\alpha_2$时，$T_0(\\alpha) \\preceq T_0(\\alpha_1) = T_1 \\preceq T_0 $\n",
    "\n",
    "&emsp;&emsp;所以，$T_0(\\alpha)=T_1(\\alpha)=T_1$，该式说明$T_1$是区间$[\\alpha_1, \\alpha_2)$的最优子树。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;依次类推，子树$T_i$是区间$[\\alpha_i,\\alpha_{i+1})$里最优的，原结论得证。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
